#include <iostream>     // std::cout, std::cin
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include <limits>
#include "backtracking.h"

using namespace std;


vector <int> camino_u_v_backtracking;
int w1_backtracking, w2_backtracking;


void backtracking()
{
  w1_backtracking = 0; 
  w2_backtracking = numeric_limits<int>::max();
  
  vector< Nodo *> camino_u_v;
  camino_u_v.resize(n);
  camino_u_v[0] = &nodos[u];
  recursion(camino_u_v, 0, 0, 0);
  return;
}


void recursion(vector <Nodo*> &camino_u_n, int pos, int w1, int w2)
{
  int k = camino_u_n[pos]->numero;
  pos++; 
  if (k == v)
  {
    if (w2 < w2_backtracking)
    {
      camino_u_v_backtracking.resize(pos);
      for (int i = 0; i < pos; i++)
      {
        camino_u_v_backtracking[i] = camino_u_n[i]->numero;
      }
      w1_backtracking = w1;
      w2_backtracking = w2;
    }
    return;
  }
  else
  {
    for(int i = 0; i < nodos[k].adyacentes.size(); i++)
    { 
      Nodo * adyacente = nodos[k].adyacentes[i];
      if(w1+nodos[k].w[adyacente->numero].first <= K && w2 < w2_backtracking)
      {
        if (no_esta_en_camino(adyacente, camino_u_n, pos-1))
        { 
          camino_u_n[pos] = adyacente;
          recursion(camino_u_n, pos, (w1+nodos[k].w[adyacente->numero].first),(w2+nodos[k].w[adyacente->numero].second));
        }
      }
    }
  }
}


bool no_esta_en_camino(Nodo * nodo, vector <Nodo *> &camino_u_n, int pos)
{
  for (int i = 0; i < pos; i++)
  { 
    if (camino_u_n[i]->numero == nodo->numero)
    {
      return false;
    }
  }
  return true;
}















